We present a novel method to compute the approximate global penetration depth(PD) between two non-convex geometric models. Our approach consists of twophases: offline precomputation and run-time queries. In the first phase, ourformulation uses a novel sampling algorithm to precompute an approximation ofthe high-dimensional contact space between the pair of models. As compared withprior random sampling algorithms for contact space approximation, ourpropagation sampling considerably speeds up the precomputation and yields ahigh quality approximation. At run-time, we perform a nearest-neighbor queryand local projection to efficiently compute the translational or generalizedPD. We demonstrate the performance of our approach on complex 3D benchmarkswith tens or hundreds of thousands of triangles, and we observe significantimprovement over previous methods in terms of accuracy, with a modestimprovement in the run-time performance.
展开▼
